package com.wm.algorithm.stack;

import java.util.Stack;

/**
 * @ClassName: SimpleStack
 * @Description: 简单级
 * @Author: Deamer
 * @Date: 2022/4/12 6:05
 **/
public class SimpleStack {

    /**
     * 20. 有效的括号
     * https://leetcode-cn.com/problems/valid-parentheses/
     * 方法二：栈
     * 思路：遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配
     *
     * @param s
     * @return
     */
    // O(n)/O(n) n：s的字符集/ n：栈中的字符数
    public boolean isValid2(String s) {
        // 如果括号是奇数直接返回
        if (s.length() % 2 == 1) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                // 字符 c 是右括号  注意stack.pop()就跳出一个元素了
                if (stack.isEmpty() || stack.pop() != getLeft(c)) {
                    // 和最近的左括号不匹配
                    return false;
                }
            }
        }
        // 是否所有的左括号都被匹配了
        return stack.isEmpty();
    }

    // 根据右括号获取左括号
    private char getLeft(char right) {
        if (right == ')') {
            return '(';
        } else if (right == '}') {
            return '{';
        }
        return '[';
    }

    /**
     * 20. 有效的括号
     * https://leetcode-cn.com/problems/valid-parentheses/
     * 方法一：栈
     * 思路：直接判断括号
     *
     * @param s
     * @return
     */
    // O(n)/O(n) n：s的字符集； /  n：栈中的字符数
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        Stack<Character> chars = new Stack<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '{' || c == '[' || c == '(') {
                chars.push(c);
            } else if (chars.isEmpty() || (c == '}' && chars.pop() != '{') || (c == ']' && chars.pop() != '[') || (c == ')' && chars.pop() != '(')) {
                return false;
            }
        }
        return chars.isEmpty();
    }
}
